This invention relates in general to methods and apparatus for the generation of random selections, and in particular to methods and apparatus for the selection of random values from a fixed set which may not be sequential.
The term "sequential" is used herein to denote "natural series", such as the set of integers. Examples of non-sequential series include: {1, 2, 3, 5, 8, 9}, {0.1, 0.3, 0.435, 0.9999, 7.7333}, and {-5.01, -0.2, 3, 4, 5}.
Many applications require random number selection from a set of numbers which may be non-sequential, especially applications where a limited finite amount of selection time is a constraint. Such applications include, but are not limited to, frequency hopping devices (e.g., radios), encryption technologies, and waveform simulators.
The problems to be solved include:
(1) the generation of random values from a set of values which may be sequential or non-sequential, very large, and comprised of integer and/or floating point values;
(2) use of an apparatus and method which is not dependent upon any known mapping between the set of values and another set (such as the set of natural numbers);
(3) completion of each random value selection within a determinate time;
(4) use of an apparatus and method which require an amount of memory substantially smaller than storing all values of the set in a large array.
One brute-force solution is to treat a set as though it were sequential between the smallest value and the largest value of the set. A series of random values could then be generated until one of the random values matches a member of the set. This solution is unsatisfactory, however, since the process could take forever to generate a value which matches a member of the set.
Another possible solution is to create an array of all possible values within the set and to generate a random index into the set. Although this would be relatively efficient for small sets, the size of the memory would become a constraining limitation on the maximum size of a set.
Still another possible solution would be to use a forced mapping of random numbers onto the values in the set. This solution would not necessarily have a known distribution of output values, however, and would not provide a generalized solution to the problem.
The generation of random values, as applied to frequency hopping radios, must result in the generation of frequencies at very fast rates, without requiring large amounts of memory or processor throughput. For example, it may be desired to generate frequencies of 30.000 MHz to 39.995 MHz on 5 kHz spacing without using 30.030 MHz or 31.005 MHz .
Some hopping radios use repetitive lookup tables, but this method produces an identifiable repetitive hopping signature. Some hopping radios use pre-built frequency tables, but this method limits the amount of time the radio can transmit or receive continuously. Some hopping radios use on the fly generation, but such a method consumes enormous amounts of memory and throughput capacity and is not particularly fast. Furthermore, some on the fly generation techniques cannot handle non-sequential frequency sets.